#include <stdio.h>
void insertion_sort(int unsorted_array[], int num_elements)
{
    int box;
    int j;
    for (int i = 0; i < num_elements; ++i) {
        box = unsorted_array[i];
        j = i - 1;
        while (j>=0 && box<unsorted_array[j]){
            unsorted_array[j+1] = unsorted_array[j];
            unsorted_array[j] = box;
            j--;
        }

    }
}

void quick_sort1(const int list1[], int list2[], int start, int start1, int num_ele)
{
    for (int i = start, j = start1, k = num_ele; k > 0; i++, j++, k--)
    {
        list2[j] = list1[i];
    }
}
void quick_sort(int unsorted_array[], int num_elements)
{
    int base = unsorted_array[0];
    if (num_elements > 1)
    {
        int small[num_elements], big[num_elements];
        int small_size = 0, big_size = 0;
        for (int i = 1; i < num_elements; i++)
        {
            if (base >= unsorted_array[i])
            {
                small[small_size] = unsorted_array[i];
                small_size++;
            }
            else
            {
                big[big_size] = unsorted_array[i];
                big_size++;
            }
        }
        unsorted_array[small_size] = base;
        quick_sort(small, small_size);
        quick_sort(big, big_size);
        quick_sort1(small, unsorted_array, 0, 0, small_size);
        quick_sort1(big, unsorted_array, 0, small_size + 1, big_size);
    }
}

void Swap(int *a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heap_down(int* unsorted_array,int i, int c){
    int child;
    int tp;
    for(tp=unsorted_array[i]; 2*i+1<c;i=child){
        child = 2*i+1;
        if(child!=c-1 && unsorted_array[child+1]>unsorted_array[child]){
            child++;
        }
        if(tp<unsorted_array[child]){
            unsorted_array[i]=unsorted_array[child];
            unsorted_array[child]=tp;
        }
        else{
            break;
        }
    }
}


//������
void heap_Sort(int unsorted_array[], int num_elements){
    int i;


    for(i=num_elements/2;i>=0;i--){
        heap_down(unsorted_array, i, num_elements);
    }
    for(i=num_elements-1;i>0;i--){
        Swap(&unsorted_array[0],&unsorted_array[i]);
        heap_down(unsorted_array,0,i);
    }
}

int main()
{
    int a[] = {1, 9, 8, 7, 6, 5, 0, 2, 3, 4};

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }

    printf("\n");
    insertion_sort(a, 10);
    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
printf("\n");
    quick_sort(a, 10);
    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
   heap_Sort(a, 10);
    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
}

